package 中等.树;

import java.util.Arrays;

/**
 * 给你一个字符串数组 words 和一个字符串 target。
 * 如果字符串 x 是 words 中 任意 字符串的
 * 前缀，则认为 x 是一个 有效 字符串。
 * 现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字
 * 符串数量。如果无法通过这种方式形成 target，则返回 -1。
 *
 * @ https://leetcode.cn/problems/minimum-number-of-valid-strings-to-form-target-i/description/
 * @date 2024/09/16
 */
public class 形成目标字符串需要的最少字符串数I_3291 {

    public static void main(String[] args) {

        System.out.println(new 形成目标字符串需要的最少字符串数I_3291()
                .minValidStrings(
                        new String[]{"abc", "aaaaa", "bcdef"},
                        "aabcdabc"));

    }

    private int[] memo;

    /**
     * 字典树+记忆化
     */
    public int minValidStrings(String[] words, String target) {
        memo = new int[target.length()];
        Arrays.fill(memo, Integer.MAX_VALUE);
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

        dfs(trie, 0, target);
        return memo[0] >= Integer.MAX_VALUE / 2 ? -1 : memo[0];
    }

    private int dfs(Trie trie, int idx, String target) {
        if (idx >= target.length()) {
            return 0;
        }
        if (idx < target.length() &&
                trie.child[target.charAt(idx) - 'a'] == null) {
            return Integer.MAX_VALUE / 2;
        }
        if (memo[idx] != Integer.MAX_VALUE) {
            return memo[idx];
        }
        int min = Integer.MAX_VALUE;
        Trie cur = trie;
        for (int i = idx; i < target.length(); i++) {
            if (cur.child[target.charAt(i) - 'a'] != null) {
                min = Math.min(min, 1 + dfs(trie, i + 1, target));
            } else {
                break;
            }
            cur = cur.child[target.charAt(i) - 'a'];
        }

        return memo[idx] = min;
    }

    static class Trie {

        private Trie[] child = new Trie[26];

        private void insert(String word) {
            Trie cur = this;

            for (int i = 0; i < word.length(); i++) {

                if (cur.child[word.charAt(i) - 'a'] == null) {
                    cur.child[word.charAt(i) - 'a'] = new Trie();
                }
                cur = cur.child[word.charAt(i) - 'a'];
            }
        }
    }
}
